package com.sheng.leetcode.year2023.month11.day09;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author by ls
 * @date 2023/11/9
 * <p>
 * 2258. 逃离火灾<p>
 * <p>
 * 给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ，它表示一个网格图。每个格子为下面 3 个值之一：<p>
 * 0 表示草地。<p>
 * 1 表示着火的格子。<p>
 * 2 表示一座墙，你跟火都不能通过这个格子。<p>
 * 一开始你在最左上角的格子 (0, 0) ，你想要到达最右下角的安全屋格子 (m - 1, n - 1) 。<p>
 * 每一分钟，你可以移动到 相邻 的草地格子。每次你移动 之后 ，着火的格子会扩散到所有不是墙的 相邻 格子。<p>
 * 请你返回你在初始位置可以停留的 最多 分钟数，且停留完这段时间后你还能安全到达安全屋。<p>
 * 如果无法实现，请你返回 -1 。如果不管你在初始位置停留多久，你 总是 能到达安全屋，请你返回 109 。<p>
 * 注意，如果你到达安全屋后，火马上到了安全屋，这视为你能够安全到达安全屋。<p>
 * 如果两个格子有共同边，那么它们为 相邻 格子。<p>
 * <p>
 * 示例 1：<p>
 * 输入：grid = [[0,2,0,0,0,0,0],[0,0,0,2,2,1,0],[0,2,0,0,1,2,0],[0,0,2,2,2,0,2],[0,0,0,0,0,0,0]]<p>
 * 输出：3<p>
 * 解释：上图展示了你在初始位置停留 3 分钟后的情形。<p>
 * 你仍然可以安全到达安全屋。<p>
 * 停留超过 3 分钟会让你无法安全到达安全屋。<p>
 * <p>
 * 示例 2：<p>
 * 输入：grid = [[0,0,0,0],[0,1,2,0],[0,2,0,0]]<p>
 * 输出：-1<p>
 * 解释：上图展示了你马上开始朝安全屋移动的情形。<p>
 * 火会蔓延到你可以移动的所有格子，所以无法安全到达安全屋。<p>
 * 所以返回 -1 。<p>
 * <p>
 * 示例 3：<p>
 * 输入：grid = [[0,0,0],[2,2,0],[1,2,0]]<p>
 * 输出：1000000000<p>
 * 解释：上图展示了初始网格图。<p>
 * 注意，由于火被墙围了起来，所以无论如何你都能安全到达安全屋。<p>
 * 所以返回 109 。<p>
 * <p>
 * 提示：<p>
 * m == grid.length<p>
 * n == grid[i].length<p>
 * 2 <= m, n <= 300<p>
 * 4 <= m * n <= 2 * 10^4<p>
 * grid[i][j] 是 0 ，1 或者 2 。<p>
 * grid[0][0] == grid[m - 1][n - 1] == 0<p>
 */
public class LeetCode2258 {

    @Test
    public void test01() {
        int[][] grid = {{0, 2, 0, 0, 0, 0, 0}, {0, 0, 0, 2, 2, 1, 0}, {0, 2, 0, 0, 1, 2, 0}, {0, 0, 2, 2, 2, 0, 2}, {0, 0, 0, 0, 0, 0, 0}};
//        int[][] grid = {{0, 0, 0, 0}, {0, 1, 2, 0}, {0, 2, 0, 0}};
//        int[][] grid = {{0, 0, 0}, {2, 2, 0}, {1, 2, 0}};
        System.out.println(new Solution().maximumMinutes(grid));
    }
}

class Solution {
    int[][] dirs = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    int n, m;
    boolean ok;
    int[][] g, fg, pg;

    public int maximumMinutes(int[][] grid) {
        g = grid;
        n = g.length;
        m = g[0].length;
        fg = new int[n][m];
        pg = new int[n][m];
        if (!check(0)) {
            return -1;
        }
        int l = 0, r = n * m;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (check(mid)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return r == m * n ? (int) 1e9 : r;
    }

    boolean check(int t) {
        ok = false;
        Deque<int[]> frie = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                fg[i][j] = pg[i][j] = 0;
                if (g[i][j] == 1) {
                    fg[i][j] = 1;
                    frie.addLast(new int[]{i, j});
                }
            }
        }
        while (t-- > 0) {
            // 先执行 t 秒的火势蔓延
            update(frie, true, 0);
        }
        if (fg[0][0] != 0) {
            return false;
        }
        Deque<int[]> people = new ArrayDeque<>();
        pg[0][0] = 1;
        people.addLast(new int[]{0, 0});
        while (!people.isEmpty()) {
            // 先火后人, 同步进行
            update(frie, true, 1);
            update(people, false, 1);
            if (ok) {
                return true;
            }
        }
        return false;
    }

    void update(Deque<int[]> deque, boolean isFrie, int offset) {
        int sz = deque.size();
        while (sz-- > 0) {
            int[] info = deque.pollFirst();
            int x = info[0], y = info[1];
            for (int[] dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                    continue;
                }
                if (g[nx][ny] == 2) {
                    continue;
                }
                if (isFrie) {
                    if (fg[nx][ny] != 0) {
                        continue;
                    }
                    fg[nx][ny] = fg[x][y] + offset;
                } else {
                    if (nx == n - 1 && ny == m - 1 && (fg[nx][ny] == 0 || fg[nx][ny] == pg[x][y] + offset)) {
                        // 火尚未到达 或 同时到达
                        ok = true;
                    }
                    if (fg[nx][ny] != 0 || pg[nx][ny] != 0) {
                        continue;
                    }
                    pg[nx][ny] = pg[x][y] + offset;
                }
                deque.addLast(new int[]{nx, ny});
            }
        }
    }
}
